package blue_bridge_cup_learning.data_struct_code;

public class LinkList {
    private Node head;

    private static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    public LinkList() {
        this.head = new Node(0);
    }

    // 头插法
    public void addNode_head(int data) {
        Node newNode = new Node(data);
        newNode.next = head.next;
        head.next = newNode;
    }

    // 打印链表
    public void printList() {
        Node current = head.next;
        while (current != null) {
            if (current.next != null) {
                System.out.print(current.data + "->");
            } else {
                System.out.print(current.data);
            }
            current = current.next;
        }
        System.out.println();
    }

    public void add_Node_tail(int data) {

        Node newNode = new Node(data);
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    public void createLinkList_head(int number, LinkList linkList) {
        for (int i = 0; i < number; i++) {
            linkList.addNode_head(i + 1);
        }
    }

    public void createLinkList_tail(int number, LinkList linkList) {
        for (int i = 0; i < number; i++) {
            linkList.add_Node_tail(i + 1);
        }
    }

    public void InsertNode(int index, int data) {
        Node newNode = new Node(data);
        Node current = this.head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        newNode.next = current.next;
        current.next = newNode;
    }

    public void deleteNode(int index) {
        Node current = this.head;
        // 循环完成后，current指向要删除节点的前一个节点
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        current.next = current.next.next;
    }

    public LinkList ReverseLinkList(LinkList List) {
        Node current = List.head.next;
        Node newNode = null;
        // 不断循环寻找新的节点
        while (current != null) {
            Node next = current.next;
            // 将当前节点进行反转
            current.next = newNode;
            // 将反转后的节点赋值给newNode
            newNode = current;
            // 将下一个节点赋值给current
            current = next;
        }
        List.head.next = newNode;
        return List;
    }

    public void mergeSortedList(LinkList List1, LinkList List2) {
        Node current1 = List1.head.next;
        Node current2 = List2.head.next;
        Node current = this.head;
        while (current1 != null && current2 != null) {
            if (current1.data < current2.data) {
                current.next = current1;
                current1 = current1.next;
            } else {
                current.next = current2;
                current2 = current2.next;
            }
            current = current.next;
        }
        if (current1 != null) {
            current.next = current1;
        }
        if (current2 != null) {
            current.next = current2;
        }
    }

    public static void main(String[] args) {
        LinkList linkList = new LinkList();
        linkList.printList();
        // 使用尾插法创建1到10的链表
        linkList.createLinkList_tail(10, linkList);
        linkList.printList();
        // 使用头插法创建1到10的链表
        // LinkList linkList2 = new LinkList();
        // linkList2.createLinkList_head(10, linkList2);
        // linkList2.printList();
        // 在第3个位置插入11
        linkList.InsertNode(3, 11);
        linkList.printList();
        // 删除第3个节点
        linkList.deleteNode(3);
        linkList.printList();
        // 反转链表
        LinkList linkList2 = new LinkList();
        linkList2.createLinkList_tail(5, linkList2);
        System.out.println("反转前");
        linkList2.printList();
        linkList2.ReverseLinkList(linkList2);
        System.out.println("反转后");
        linkList2.printList();
        // 创建两个有序链表
        LinkList linkList3 = new LinkList();
        linkList3.createLinkList_tail(5, linkList3);
        LinkList linkList4 = new LinkList();
        linkList4.createLinkList_tail(5, linkList4);
        System.out.println("有序链表1");
        linkList3.printList();
        System.out.println("有序链表2");
        linkList4.printList();
        linkList.mergeSortedList(linkList3, linkList4);
        System.out.println("合并后");
        linkList.printList();
    }
}
